package com.tgy.algorithm.base;

public class _查找两个相交链表第一个相交的节点 {

    public static Node[] generateLinked() {


        // 1 2 3
        int[] nums = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
        int[] nums01 = {20,21,22,23,24};

        Node oneNode = generateLinked2(nums);
        Node twoNode = generateLinked2(nums01);

        Node twoLastNode = twoNode;

        while (twoLastNode != null && twoLastNode.next != null) {
            twoLastNode = twoLastNode.next;
        }

        twoLastNode.next = oneNode.next.next.next.next;
        return new Node[]{oneNode, twoNode};
    }

    public static Node generateLinked2(int[] nums) {

        if (nums == null || nums.length == 0) {
            return null;
        }
        Node head = new Node(nums[0], null);
        Node cur = head;
        for (int i = 1; i < nums.length; i++) {
            Node next = new Node(nums[i], null);
            cur.next = next;
            cur = next;
        }

        return head;
    }

    public static Node getFirstCrosNode(Node[] nodes) {

        if (nodes == null || nodes.length != 2) {
            return null;
        }

        Node oneNode = nodes[0];
        Node onePreNode = null;
        Node twoNode = nodes[1];
        Node twoPreNode = null;
        int oneLen = 0;
        while (oneNode != null) {
            oneLen++;
            onePreNode = oneNode;
            oneNode = oneNode.next;
        }

        int twoLen = 0;
        while (twoNode != null) {
            twoLen++;
            twoPreNode = twoNode;
            twoNode = twoNode.next;
        }

        if (onePreNode != twoPreNode) {
            return null;
        }

        int maxLen = Math.max(oneLen,twoLen);
        Node preRunNode = null;
        int preRunLen = 0;
        Node postRunNode = null;
        if (oneLen == maxLen) {
            preRunNode = nodes[0];
            postRunNode  = nodes[1];
            preRunLen = oneLen - twoLen;
        }else {
            preRunNode  = nodes[1];
            postRunNode  = nodes[0];
            preRunLen = twoLen - oneLen;
      }

        while(preRunLen > 0) {
        preRunNode = preRunNode.next;
        preRunLen--;
    }

        while(preRunNode != postRunNode) {
            preRunNode = preRunNode.next;
            postRunNode = postRunNode.next;
        }

        return preRunNode;
    }

    public static void main(String[] args) {

        Node[] nodes = generateLinked();
        System.out.println(nodes);
        Node firstCrosNode = getFirstCrosNode(nodes);
        System.out.println(firstCrosNode);
    }

}
